package com.test.sort;

/***
 * 快速排序
 * 思路：
 * 1.定义一个中间值
 * 2.一个left指针，一个rigth指针
 * 3.left向右移动，rigth向左移动，left大于中间值且ritght小于中间值的情况下交换，并且left指针小于rigth指针
 * 4.如果各个指针没有移动到最左或者最右那么递归遍历
 */

public class QuickSort {
    public static void sort(int[] arr, int left, int rigth) {
        int l = left;
        int r = rigth;
        int mid = (left + rigth) / 2;
        int midVal = arr[mid];
        int temp;
        while (l < r) {
            while (arr[l] < midVal) {
                l++;
            }
            while (arr[r] > midVal) {
                r--;
            }
            if (l >= r) break;//必须大于等于否者可能会越过==
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        if (l == r) {//如果相等情况下没有移动俩指针那么可能会造成重复排序问题
            l++;
            r--;
        }
        if (l < rigth) {
            sort(arr, l, rigth);
        }
        if (r > left) {
            sort(arr, left, r);
        }
    }

    public static void main(String[] args) {
        int arr[] = {3, 4, 5, 2, 8, 1};
        sort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}
